In JPEG, which is an international standard coding system for still images, lossless encoding mode was standardized such that images after compression or decompression would be exactly identical to the original images. However, techniques for lossless transformation had not been studied sufficiently at the time, and it was not possible to implement lossless transformation using DCT. Therefore, using a technique different from DCT-based block transform coding, lossless encoding was implemented by a pixel-based method known as predictive coding.
Later, JPEG-LS, a standard coding technique dedicated to lossless encoding was standardized. The JPEG2000 standardized subsequently implemented both lossless transformation and typical lossy transformation using a technique called wavelet transform, enabling both lossless encoding without degradation and lossy encoding with some degradation.
Compression and transformation processes of image data are roughly divided into three types: spatial conversion process (DCT, wavelet transform, etc.), quantizing process, and entropy encoding process. Among them, the entropy encoding process consists in converting a collection of quantized values (information) into other codes such as Huffman codes, and thereby converting the bit count of the information to a bit count close to that of entropy included in the information. It is a sort of lossless data transformation process.
On the other hand, a quantizing process, which is a process of reducing the amount of information, allows a compression ratio to be controlled. Basically, it is a lossy transformation. Thus, to carry out a transform coding/compression process in a lossless manner, the quantizing process must not be used. However, any decimal part produced by a spatial conversion process must be quantized. Otherwise, the amount of data will increase after the compression.
Any decimal part produced by a spatial conversion process will be converted into an integer using a quantizing step of “1,” resulting in signal degradation. Thus, there is no guarantee that the data after the decompression will be identical to the original data.
After all, it can be seen that in order to implement lossless encoding, it is necessary to perform entropy encoding directly instead of quantizing a value (lossless transform coefficient) obtained by a spatial conversion process that outputs integer values whose reversibility is guaranteed. However, it might be said that a quantizing process is performed using a quantizing step of “1” because the transform coefficient is maintained as it is even in that case.
In this way, to implement lossless encoding, a spatial conversion process that outputs integer values whose reversibility is guaranteed (hereinafter referred to as lossless transformation) is indispensable.
Conventionally, ladder networks are available as a technique for implementing lossless transformation (See, for example, F. Bruekers and A. Enden “New Networks for Perfect Inversion and Perfect Reconstruction,” IEEE JSAC, vol. 10, no. 1, pp. 130-137, January 1992). A ladder network is obtained by decomposing a two-point rotational transformation matrix into three triangular matrices, replacing each triangular matrix with a ladder operation, and then introducing a rounding process into the ladder operations.
An expansion of the ladder network into a four-point orthogonal transformation is described in an article by Kunitoshi KOMATSU and Kaoru SEZAKI, “Reversible DCT and Its Application to Image Coding,” Shingaku-Giho, IE97-83, pp. 1-6, November 1997.
Lossless two-point rotational transformation and lossless four-point orthogonal transformation will be described in more detail below.
A two-point rotational transformation matrix can be decomposed into a product of three triangular matrices whose diagonal elements are “1.”
      (                                        cos            ⁢                                                  ⁢            θ                                                sin            ⁢                                                  ⁢            θ                                                                          -              sin                        ⁢                                                  ⁢            θ                                                cos            ⁢                                                  ⁢            θ                                )    =            (                                    1                                              tan              ⁢                                                          ⁢                              θ                2                                                                          0                                1                              )        ⁢          (                                    1                                0                                                                              -                sin                            ⁢                                                          ⁢              θ                                            1                              )        ⁢          (                                    1                                              tan              ⁢                                                          ⁢                              θ                2                                                                          0                                1                              )      
If two items of input data are considered to be two legs of a ladder, operations on triangular matrices whose diagonal elements are “1” structurally correspond to rungs of the ladder. That is, since operations on off-diagonal elements involve multiplying one of the inputs by the values of the off-diagonal elements and adding the product to the other input, they look like rungs of the ladder when represented by a signal flow graph. Thus, two-point rotational transformation can be represented by three-rung ladder operations as shown in FIG. 1A.
As shown in FIG. 1B, by rounding the result of the multiplication process in each ladder operation to an integer, it is possible to easily implement lossless transformation from integer values to integer values. Thus, a lossless transformation by means of ladder operations can be provided by three types of processor: multiplication processors, rounding processors, and addition processors (or subtraction processors in some cases). In FIG. 1B, reference numerals 111, 121, and 131 denote multiplication processors; 113, 123, and 133 denote rounding processors; and 115, 125, and 135 denote addition processors. When a rotational angle is θ, multiplication factors for the multipliers 111, 121, and 131 are TAN(θ/2), −SIN(θ) and TAN(θ/2), respectively.
When the result of multiplication in each step of ladder operations is rounded to an integer, a rounding error always occurs unless the result of multiplication is an integer. The errors which occur in ladder operations are superimposed over output data.
Conventionally, a four-point orthogonal transformation consisting of four two-point rotational transformations is configured as shown in FIG. 2. Here, reference numerals 201 to 204 denote the two-point rotational transformations, each of which consists of a three-rung ladder operation as shown in FIG. 1B. Looking at the entire four-point orthogonal transformation, there are 12 steps of ladder operations. Similarly, rounding is repeated 12 times. Naturally, the rounding error increases in proportion to the number of rounding operations.
On the other hand, the technique described in the article by Kinutoshi KOMATSU and Kaoru SEZAKI, “Reversible DCT and Its Application to Image Coding,” Shingaku-Giho, IE97-83, pp. 1-6, November 1997” implements lossless transformation by dividing a four-point orthogonal transformation into five ladder operations expanded to accommodate four-dimensional operations. Since an n-dimensional ladder operation involves n−1 multiplication operations, a four-point orthogonal transformation requires (4−1)×5=15 multiplication operations. However, thanks to the nature of the ladder operation, the rounding can be reduced greatly. In the case of a multi-dimensional ladder operation, since outputs (data to be added) of a ladder operation are collected together, the rounding can be performed after adding up the data, making it possible to get by with a single rounding operation per ladder operation. Thus, the four-point orthogonal transformation according to the above technique can get by with five rounding operations.
As described above, since a lossless transformation requires special operations called ladder operations in order to guarantee its reversibility, fast computational algorithms on which many studies have been conducted cannot be applied to it. This makes it difficult to reduce the amount of computation. In other words, conventional lossless transformations require special operations and are not suitable for fast computation. Also, they involve a large number of rounding operations, resulting in a large rounding error.